package Sort;

/**
 * @author yyq
 * @create 2021-10-16 15:14
 * 归并排序
 *
 */
public class MergeSort {

    static int[] temp=new int[100];
    
    public static void mergesort(int left,int right,int[] a){
        if(left<right){
            int mid=(right+left)/2;
            mergesort(left,mid,a);
            mergesort(mid+1,right,a);
            merge(left,right,mid,a);
        }

    }

    private static void merge(int left, int right, int mid, int[] a) {
        int low=left;
        int high=mid+1;
        int loc=left;
        while(loc<=right){
            if(low>mid){
                temp[loc]=a[high];
                loc++;
                high++;
                continue;
            }
            if(high>right){
                temp[loc]=a[low];
                loc++;
                low++;
                continue;
            }
            if(a[low]<=a[high]){
                temp[loc]=a[low];
                loc++;
                low++;
            }
            if(a[high]<a[low]){
                temp[loc]=a[high];
                loc++;
                high++;
            }
        }
        for (int i=left;i<=right;i++){
            a[i]=temp[i];
        }

    }

    public static void main(String[] args) {
        int[] a={2,1321,231,6,4,3,2,1,5};
        mergesort(0,a.length-1,a);
        for (int i : a) {
            System.out.println(i);
        }
    }

}
